package offer;

import java.util.HashMap;
import java.util.Set;

public class offerII_0050 {
    public int pathSum(TreeNode root, int targetSum) {
        int[] num=new int[1];
        HashMap<Long, Integer> map=new HashMap<>();
        map.put(0L,1);
        dp(root,0,targetSum,map,num);
        return num[0];
    }
    public void dp(TreeNode node, long sum, int target, HashMap<Long, Integer> map,int[] num){
        if(node==null) return;
        if(map.containsKey(sum+ node.val-target)){
            num[0]+=map.get(sum+ node.val-target);
        }
        if(map.containsKey(sum+node.val)){
            map.put(sum+node.val,map.get(sum+node.val)+1);
        }
        else map.put(sum+node.val,1);
        dp(node.left,sum+node.val,target,map,num);
        dp(node.right,sum+node.val,target,map,num);
        map.put(sum+node.val,map.get(sum+node.val)-1);
    }
}
